/*
 * Author: 李昀烛 1300012798
 *
 * Outline:
 * 从肖思佳的版本改造而来，核心在于使用并查集，并离线询问。
 *
 * Optimization:
 * 注意到询问中的生日满足某种单调性：生日更晚的query对应的生成图，
 * 永远是生日更早的query对应生成图的子图。所以不妨对query按照生日
 * 进行排序，按照从晚到早的顺序离线处理询问。那么接下来我们就需要
 * 知道对于每一个生日的询问，哪些边应该在图中，很直观的，边连接的
 * 两个人的生日都应该小于等于该询问中要求的生日，那么这条边就在图中，
 * 所以我们就可以对边按照两个端点中生日更早的人进行排序，对应询问，
 * 依次加边使用并查集维护集合即可。但是因为有多个tag需要进行处理，
 * 所以需要将每个人拆成很多点，分别对应他含有的不同tag，那么在加边时，
 * 需要处理两人所有共同的tag，对应不同人的不同tag进行合并。最后
 * 用一个set维护每个tag所包含最大联通块的大小就可以很快的处理了。
 *
 * Performance:
 * 时间复杂度大概是O(num_relation * num_tag)，运行10k的数据大概需要0.7秒。
 */
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <set>

using namespace std;

#define LENGTH 1000						
#define K_LIMIT 20

string birthday_limit;
int ans_num;

char buf[LENGTH];
string data_path;
int data_size;
string query_file;
string answer_file;

int count_person;
unordered_map<int, int> personID;
unordered_map<int, string> tag;
vector<vector<int> > interest;
unordered_map<int, string> birthday;
unordered_map<int, string> tag_name;

unordered_map<int, int> tag_size;

struct TagSize
{
    int tagID, size;

    TagSize() {} TagSize(int _tagID, int _size)
    { tagID = _tagID, size = _size; }

    bool operator < (const TagSize tmp) const
    {
        if(size == tmp.size) 
            return tag_name[tagID] < tag_name[tmp.tagID];
        return size > tmp.size;
    }
};

set<TagSize> final_set;

struct Edge
{
    int a, b;
    Edge() {} Edge(int _a, int _b)
    { a = _a, b = _b; }
};

vector<Edge> relation;

struct PersonTag
{
    int ID, tag;
    PersonTag() {} PersonTag(int _ID, int _tag)
    { ID = _ID, tag = _tag; }

    bool operator == (const PersonTag tmp) const
    { return ID == tmp.ID && tag == tmp.tag; }

    bool operator < (const PersonTag tmp) const
    {
        if(ID == tmp.ID) return tag < tmp.tag;
        return ID < tmp.ID;
    }

};

map<PersonTag, PersonTag> union_fa;
map<PersonTag, int> union_size;

struct PersonBirth
{
    int index; string birthday;
    PersonBirth() {} PersonBirth(int _index, string _birthday)
    { index = _index, birthday = _birthday; }
};

vector<PersonBirth> person_birth;

struct Query
{
    int ans_num, index; string birthday_limit;
    vector<string> ans;

    Query() {} Query(int a, string b, int c)
    { ans_num = a, birthday_limit = b, index = c; }
};

int count_query;
vector<Query> query;

inline bool comparePersonByBirthday(const PersonBirth &a, const PersonBirth &b)
{
    return a.birthday > b.birthday;
}

inline bool compareRelationByBirthday(const Edge &x, const Edge &y)
{
    return min(birthday[x.a], birthday[x.b]) > min(birthday[y.a], birthday[y.b]);
}

inline bool compareQueryByBirthday(const Query &a, const Query &b)
{
    return a.birthday_limit > b.birthday_limit;
}

inline bool compareQueryByIndex(const Query &a, const Query &b)
{
    return a.index < b.index;
}

void getPersonIDandBirthday()
{
	string person_data_file = data_path + "person.csv";
	FILE *f_person = fopen(person_data_file.c_str(), "r");

	fgets(buf, LENGTH, f_person);
	while(fgets(buf, LENGTH, f_person) != NULL)
	{
		int i = 0;
		string tmp;
		while(1)
		{
			if(buf[i] == '|') { i++; break;}
			tmp += buf[i];
			i++;
		}
		personID[atoi(tmp.c_str())] = ++count_person;
		int count_seg = 1;
		while(1)
		{
			if(count_seg == 4) break;
			if(buf[i] == '|') count_seg++;
			i++;
		}
		tmp = "";
		while(1)
		{
			if(buf[i] == '|') break;
			tmp += buf[i];
			i++;
		}
		birthday[count_person] = tmp;

        person_birth.push_back(PersonBirth(count_person, tmp));
	}

    sort(person_birth.begin(), person_birth.end(), comparePersonByBirthday);

	fclose(f_person);
}

void gatTag()
{
	string tag_data_file = data_path + "tag.csv";
	FILE *f_tag = fopen(tag_data_file.c_str(), "r");

	fgets(buf, LENGTH, f_tag);

	while(fgets(buf, LENGTH, f_tag) != NULL)
	{
		string tmp1, tmp2;
		int i = 0;
		while(1)
		{
			if(buf[i] == '|') { i++; break;}
			tmp1 += buf[i]; i++;
		}
		while(1)
		{
			if(buf[i] == '|') break;
			tmp2 += buf[i]; i++;
		}
		
		tag_name[atoi(tmp1.c_str())] = tmp2;
        tag_size[atoi(tmp1.c_str())] = 0;

        final_set.insert(TagSize(atoi(tmp1.c_str()), 0));
	}

	fclose(f_tag);
}

inline void add_edge(int a, int b)
{
	relation.push_back(Edge(a, b));
}

inline void getPersonRelation()
{
	string person_knows_person_data_file = data_path + "person_knows_person.csv";

	FILE *f_person_knows_person = fopen(person_knows_person_data_file.c_str(), "r");
	int tmp1, tmp2;
	fgets(buf, LENGTH, f_person_knows_person);
	while(fscanf(f_person_knows_person, "%d|%d", &tmp1, &tmp2) != EOF)
		add_edge(personID[tmp1], personID[tmp2]);

    sort(relation.begin(), relation.end(), compareRelationByBirthday);

    fclose(f_person_knows_person);
}

inline void getPersonInterest()
{
    interest.resize(count_person + 10);

	string person_hasInterest_tag_data_file = data_path + "person_hasInterest_tag.csv";
	FILE *f_person_hasInterest_tag = fopen(person_hasInterest_tag_data_file.c_str(), "r");

	int tmp1, tmp2;
	fgets(buf, LENGTH, f_person_hasInterest_tag);
	while(fscanf(f_person_hasInterest_tag, "%d|%d", &tmp1, &tmp2) != EOF)
    {
		interest[personID[tmp1]].push_back(tmp2);
        union_size[PersonTag(personID[tmp1], tmp2)] = 1;
        union_fa[PersonTag(personID[tmp1], tmp2)] = PersonTag(personID[tmp1], tmp2);
    }
	
    fclose(f_person_hasInterest_tag);
}

inline PersonTag findFa(PersonTag x)
{
    if(union_fa[x] == x) return x;
    return union_fa[x] = findFa(union_fa[x]);
}

inline void handleQueries()
{
    FILE *f_query = fopen(query_file.c_str(), "r");
	FILE *f_answer = fopen(answer_file.c_str(), "w");

	while(fgets(buf, LENGTH, f_query) != NULL)
    {
        buf[strlen(buf) - 1] = '\0';
        int len = sscanf(buf, "%d", &ans_num);
        birthday_limit = string(buf + len + 1);
        
        query.push_back(Query(ans_num, birthday_limit, ++count_query));
    }

    sort(query.begin(), query.end(), compareQueryByBirthday);

    int posi_relation = 0, posi_person = 0;
    for(int q = 0; q < (int)query.size(); q++)
    {
        while(posi_person < (int)person_birth.size())
        {
            int person = person_birth[posi_person].index;
            if(birthday[person] < query[q].birthday_limit)
                break;

            for(int i = 0; i < (int)interest[person].size(); i++)
            {
                int tag = interest[person][i];
                if(tag_size[tag] == 0)
                {
                    tag_size[tag] = 1;
                    final_set.erase(final_set.find(TagSize(tag, 0)));
                    final_set.insert(TagSize(tag, 1));
                }
            }

            posi_person++;
        }

        while(posi_relation < (int)relation.size())
        {
            if(min(birthday[relation[posi_relation].a], birthday[relation[posi_relation].b]) < query[q].birthday_limit) 
                break;

            for(int i = 0; i < (int)interest[relation[posi_relation].a].size(); i++)
            {
                if(union_fa.find(PersonTag(relation[posi_relation].b, interest[relation[posi_relation].a][i])) == union_fa.end())
                    continue;

                int tag = interest[relation[posi_relation].a][i];
                PersonTag x = findFa(PersonTag(relation[posi_relation].a, tag));
                PersonTag y = findFa(PersonTag(relation[posi_relation].b, tag));

                if(x == y) continue;

                union_fa[y] = x, union_size[x] += union_size[y];

                if(union_size[x] > tag_size[tag])
                {
                    final_set.erase(final_set.find(TagSize(tag, tag_size[tag])));

                    tag_size[tag] = union_size[x];
                    final_set.insert(TagSize(tag, tag_size[tag]));
                }
            }

            posi_relation++;
        }

        set<TagSize>::iterator it = final_set.begin();
        for(int i = 1; i < query[q].ans_num; i++)
            query[q].ans.push_back(tag_name[it -> tagID]), it++;
        query[q].ans.push_back(tag_name[it -> tagID]);
    }

    sort(query.begin(), query.end(), compareQueryByIndex);

    for(int i = 0; i < (int)query.size(); i++)
    {
        for(int j = 0; j < (int)query[i].ans.size() - 1; j++)
            fprintf(f_answer, "%s ", query[i].ans[j].c_str());
        fprintf(f_answer, "%s\n", query[i].ans[(int)query[i].ans.size() - 1].c_str());
    }

    fclose(f_query);
    fclose(f_answer);
}

int main(int argc, char *argv[])
{
#ifndef LOCAL
    data_path = argv[1];
    data_size = atoi(argv[2]);
    query_file = argv[3];
    answer_file = argv[4];
#else
    data_path = "../../../data/10k-network/";
    data_size = 10000;
    query_file = "../query2.in";
    answer_file = "../query2.out";
#endif

    getPersonIDandBirthday();
    gatTag();
    getPersonRelation();
    getPersonInterest();

    handleQueries();

    return 0;
}
